package ljl.codetop300;

import commons.WrongAnswer;

import java.util.Deque;
import java.util.LinkedList;

public class _678_valid_par {

  /**
   * 超时了我艹
   */
  @WrongAnswer
  static class test {
    public boolean checkValidString(String s) {
      if (s.length() == 0) return true;
      char[] chars = s.toCharArray();
      return yes(chars, 0, 0, 0);
    }
    boolean yes(char[] chars, int i, int lefts, int rights) {
      if (lefts < rights) return false;
      if (i == chars.length) return lefts == rights;
      char c = chars[i];
      if (c == '(') {
        return yes(chars, i + 1, lefts + 1, rights);
      }
      if (c == '*') {
        return yes(chars, i + 1, lefts + 1, rights)
            || yes(chars, i + 1, lefts, rights + 1)
            || yes(chars, i + 1, lefts, rights);
      }
      if (c == ')') {
        return yes(chars, i + 1, lefts, rights + 1);
      }
      return false;
    }
  }

  /**
   *
   */
  static class dp {
    public boolean checkValidString(String s) {
      int n = s.length();
      boolean[][] dp = new boolean[n][n];
      for (int i = 0; i < n; i++) {
        if (s.charAt(i) == '*') {
          dp[i][i] = true;
        }
      }
      for (int i = 1; i < n; i++) {
        char c1 = s.charAt(i - 1), c2 = s.charAt(i);
        dp[i - 1][i] = (c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*');
      }
      // 这必须是倒序，我不懂为什么
      // 他轻描淡写说了一句要注意顺序
      for (int i = n - 3; i >= 0; i--) {
        char c1 = s.charAt(i);
        for (int j = i + 2; j < n; j++) {
          char c2 = s.charAt(j);
          if ((c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*')) {
            dp[i][j] = dp[i + 1][j - 1];
          }
          for (int k = i; k < j && !dp[i][j]; k++) {
            dp[i][j] = dp[i][k] && dp[k + 1][j];
          }
        }
      }
      return dp[0][n - 1];
    }
  }

  static class copy_dp {
    public boolean checkValidString(String s) {
      int len = s.length();
      boolean[][] dp = new boolean[len][len];
      for (int i = 0; i < len; i++) {
        if (s.charAt(i) == '*') dp[i][i] = true;
      }
      for (int i = 1; i < len; i++) {
        char c1 = s.charAt(i - 1);
        char c = s.charAt(i);
        if ((c1 == '(' || c1 == '*') && (c == ')' || c == '*')) dp[i - 1][i] = true;
      }
      for (int i = len - 3; i >= 0 ; i--) {
        char c1 = s.charAt(i);
        for (int j = i + 2; j < len ; j++) {
          char c2 = s.charAt(j);
          if ((c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*')) dp[i][j] = dp[i + 1][j - 1];
          for (int k = i; !dp[i][j] && k < j; k++) {
            dp[i][j] = dp[i][k] && dp[k + 1][j];
          }
        }
      }
      return dp[0][len - 1];
    }
  }

  /**
   *
   */
  static class stack {
    public boolean checkValidString(String s) {
      Deque<Integer> leftStack = new LinkedList<Integer>();
      Deque<Integer> asteriskStack = new LinkedList<Integer>();
      int n = s.length();
      for (int i = 0; i < n; i++) {
        char c = s.charAt(i);
        if (c == '(') {
          leftStack.push(i);
        } else if (c == '*') {
          asteriskStack.push(i);
        } else {
          if (!leftStack.isEmpty()) {
            leftStack.pop();
          } else if (!asteriskStack.isEmpty()) {
            asteriskStack.pop();
          } else {
            return false;
          }
        }
      }
      while (!leftStack.isEmpty() && !asteriskStack.isEmpty()) {
        int leftIndex = leftStack.pop();
        int asteriskIndex = asteriskStack.pop();
        if (leftIndex > asteriskIndex) {
          return false;
        }
      }
      return leftStack.isEmpty();
    }
  }

  static class copy_stack {
    public boolean checkValidString(String s) {
      LinkedList<Integer> lstack = new LinkedList<>();
      LinkedList<Integer> astack = new LinkedList<>();
      for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        switch (c) {
          case '(' -> lstack.push(i);
          case ')' -> {
            if (!lstack.isEmpty()) lstack.pop();
            else if (!astack.isEmpty()) astack.pop();
            else return false;
          }
          default -> astack.push(i);
        }
      }
      while (!lstack.isEmpty() && !astack.isEmpty()) {
        if (lstack.pop() > astack.pop()) return false;
      }
      return lstack.isEmpty();
    }
  }

  /**
   *
   */
  static class greedy {
    public boolean checkValidString(String s) {
      int minCount = 0, maxCount = 0;
      int n = s.length();
      for (int i = 0; i < n; i++) {
        char c = s.charAt(i);
        if (c == '(') {
          minCount++;
          maxCount++;
        } else if (c == ')') {
          minCount = Math.max(minCount - 1, 0);
          maxCount--;
          if (maxCount < 0) {
            return false;
          }
        } else {
          minCount = Math.max(minCount - 1, 0);
          maxCount++;
        }
      }
      return minCount == 0;
    }
  }

  static class copy_greedy {
    public boolean checkValidString(String s) {
      int max = 0;
      int min = 0;
      for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        switch (c) {
          case '(' -> {
            min++;
            max++;
          }
          case ')' -> {
            min = Math.max(0, min - 1);
            if (--max < 0) return false;
          }
          default -> {
            max++;
            min = Math.max(0, min - 1);
          }
        }
      }
      return min == 0;
    }
  }
}
